/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 广度遍历，先遍历左子树为单链，再遍历右子树为单链
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
    if (root === null) return root;
    let tempRootRigth = root.right,
        stack = [],
        temp = root.left,
        point = root;

    // 前序遍历左子树
    while (stack.length > 0 || temp !== null) {
        while (temp !== null) {
            // 当前树转化为单链的指针指向位置
            point.left = null
            point.right = new TreeNode(temp.val)
            point = point.right

            stack.push(temp)
            temp = temp.left
        }

        let node = stack.pop()
        temp = node.right
    }

    // 前序遍历右子树
    temp = tempRootRigth
    while (stack.length > 0 || temp !== null) {
        while (temp !== null) {
            // 当前树转化为单链的指针指向位置
            point.left = null
            point.right = new TreeNode(temp.val)
            point = point.right

            stack.push(temp)
            temp = temp.left
        }

        let node = stack.pop()
        temp = node.right
    }
};



/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
    if (root === null) return root;

    let arr = []
    // 前序遍历存储每一个节点的引用
    preorder(root, arr)

    // 每次对一个节点进行左边赋值null，右边赋值前序遍历的后一个引用
    for (let i = 1; i < arr.length; i++) {
        let pre = arr[i - 1],
            cur = arr[i];
        
        pre.left = null;
        pre.right = cur; //建立连接
    }

};

const preorder = (root, arr) => {
    if (root === null) return
    arr.push(root)
    preorder(root.left, arr)
    preorder(root.right, arr)
}


// root = [1,2,5,3,4,null,6]
//      1
//    2   5
//   3 4   6
// 输出arr
[ [1,2,5,3,4,null,6], [2,3,4], [3], [4], [5,null,6], [6] ]
[ [1,null,2,3,4], [2,3,4], [3], [4], [5,null,6], [6] ]
[ [1,null,2,null,3], [2,null,3], [3], [4], [5,null,6], [6] ]
[ [1,null,2,null,3,null,4],[2,null,3,null,4],[3,null,4],[4],[5,null,6],[6]]
[ [1,null,2,null,3,null,4,null,5,null,6],[2,null,3,null,4,null,5,null,6],[3,null,4,null,5,null,6],[4,null,5,null,6],[5,null,6],[6]]
[ [1,null,2,null,3,null,4,null,5,null,6],[2,null,3,null,4,null,5,null,6],[3,null,4,null,5,null,6],[4,null,5,null,6],[5,null,6],[6]]




/**
 * 广度遍历，存储每个根节点的右节点，是我想象中的解法一
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
    if (root === null) return root;

    let stack = [root],
        prev = null;

    while (stack.length > 0) {
        let curNode = stack.pop();
        curNode.right && stack.push(curNode.right)
        curNode.left && stack.push(curNode.left)

        if (prev !== null) {
            prev.left = null
            prev.right = curNode
        }
        prev = curNode  // 指向下一个位置并建立连接
        // 这个写法也可以
        // if (prev !== null) {
        //     prev.left = null;
        //     prev.right = curNode;
        //     prev = prev.right
        // }else{
        //     prev = curNode
        // }
    }
};


/**
 * 空间复杂度为O(1)的解法。因为前序遍历本来就是先遍历左子树，再遍历右子树。
 * 所以把当前节点的右子树赋值到左子树的最后一个遍历的节点的右节点，再把当前节点左子树变为右子树
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
    let temp = root;
    while (temp !== null) {
        if (temp.left !== null) {
            // 左子树不为空，找到左子树遍历的最后一个右节点（如果没有右节点，是根节点，如果有右节点，那就是根节点的最右节点）
            let pre = temp.left;
            while (pre.right !== null) {
                pre = pre.right
            }
            pre.right = temp.right
            temp.right = temp.left
            temp.left = null
        }
        temp = temp.right
    }
};